package exams.list;

public class ListNodeUtilsSolution {

    /**
     * 判断链表中是否有环
     *
     * 判断给定的链表中是否有环。如果有环则返回true，否则返回false。
     * */
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }

        return false;
    }

    /**
     * 链表中环的入口结点
     *
     * 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
     * */
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null) {
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        boolean hasLoop = false;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                hasLoop = true;
                break;
            }
        }
        if(!hasLoop) {
            return null;
        }
        fast = pHead;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

    /**
     * 链表中倒数最后k个结点
     *
     * 输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
     * 如果该链表长度小于k，请返回一个长度为 0 的链表。
     * */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if(pHead == null){
            return null;
        }
        ListNode cur = pHead;
        int count = 1;
        while(cur.next != null) {
            count ++;
            cur = cur.next;
        }
        while(pHead.next != null) {
            if(count == k) {
                return pHead;
            }
            pHead = pHead.next;
            count --;
        }
        return null;
    }

    /**
     * 删除链表的倒数第n个节点
     *
     * 给定一个链表，删除链表的倒数第n个节点并返回链表的头指针
     * 例如，
     * 给出的链表为:1→2→3→4→5,n=2
     * 删除了链表的倒数第n个节点之后,链表变为1→2→3→5
     * */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        if(head == null) {
            return null;
        }
        ListNode cur = head;
        int count = 1;
        while(cur.next != null) {
            count ++;
            cur = cur.next;
        }
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        cur = newHead;
        while(cur.next != null) {
            if(count == n) {
                cur.next = cur.next.next;
                break;
            }
            cur = cur.next;
            count --;
        }

        return newHead.next;
    }

    /**
     * 两个链表的第一个公共结点
     *
     * 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
     * */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        int count = 0;
        while(cur1 != null && cur2 != null && count <= 2) {
            if(cur1 == cur2) {
                return cur1;
            }
            if(cur1.next != null) {
                cur1 = cur1.next;
            } else {
                cur1 = pHead2;
                count ++;
            }
            if(cur2.next != null) {
                cur2  = cur2.next;
            } else {
                cur2 = pHead1;
                count ++;
            }
        }

        return null;
    }

    /**
     * 链表相加
     *
     * 假设链表中每一个节点的值都在 0 - 9之间，那么链表整体就可以代表一个整数。给定两个这种链表，请生成代表两个整数相加值的结果链表。
     * 数据范围：0≤n,m≤1000000，链表任意值0≤val≤9要求：空间复杂度O(n)，时间复杂度O(n)
     * 例如：链表 1为 9->3->7，链表 2为 6->3，最后生成新的结果链表为 1->0->0->0。
     * */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        ListNode newHead = new ListNode(-1);
        head1 = reverse(head1);
        head2 = reverse(head2);

        int carry = 0;
        while(head1 != null || head2 != null) {
            int v1 = 0;
            if(head1 != null) {
                v1 = head1.val;
                head1 = head1.next;
            }
            int v2 = 0;
            if(head2 != null) {
                v2 = head2.val;
                head2 = head2.next;
            }

            int sum = v1 + v2 + carry;
            if(sum >= 10) {
                carry = 1;
            } else {
                carry = 0;
            }
            ListNode temp = new ListNode(sum%10);
            temp.next = newHead.next;
            newHead.next = temp;
        }
        if(carry == 1){
            ListNode temp = new ListNode(1);
            temp.next = newHead.next;
            newHead.next = temp;
        }

        return newHead.next;
    }

    private ListNode reverse(ListNode head) {
        ListNode p1 = head;
        ListNode p2 = null;

        while(p1 != null) {
            ListNode temp = p1.next;
            p1.next = p2;
            p2 = p1;
            p1 = temp;
        }
        return p2;
    }

    /**
     * 判断一个链表是否为回文结构
     *
     * 给定一个链表，请判断该链表是否为回文结构。
     * 回文是指该字符串正序逆序完全一致。
     * */
    public boolean isPail (ListNode head) {
        // write code here
        ListNode p1 = head;
        ListNode p2 = head.next;
        if(p1 == null || p2 == null) {
            return true;
        }

        while(p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        ListNode head2 = reverse(p1.next);

        while(head2 != null) {
            if(head.val != head2.val) {
                return false;
            }
            head = head.next;
            head2 = head2.next;
        }

        return true;
    }

    /**
     * 链表的奇偶重排
     *
     * 给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
     * 注意是节点的编号而非节点的数值。
     * */
    public ListNode oddEvenList (ListNode head) {
        // write code here
        ListNode head1 = new ListNode(-1);
        ListNode head2 = new ListNode(-1);
        int i = 1;

        ListNode p1 = head1;
        ListNode p2 = head2;

        while(head != null) {
            if(i%2 == 0) {
                p2.next = head;
                p2 = p2.next;
                p1.next = null;
            } else {
                p1.next = head;
                p1 = p1.next;
                p2.next = null;
            }
            head = head.next;
            i++;
        }
        p1.next = head2.next;

        return head1.next;
    }

    /**
     * 删除有序链表中重复的元素-I
     *
     * 删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
     * 例如：
     * 给出的链表为1→1→2,返回1→2.
     * 给出的链表为1→1→2→3→3,返回1→2→3.
     * */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        ListNode cur = head;

        while(cur != null && cur.next != null) {
            if(cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }

        return head;
    }

    /**
     * 删除有序链表中重复的元素-II
     *
     * 给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
     * 例如：
     * 给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
     * 给出的链表为1→1→1→2→3, 返回2→3.
     * */
    public ListNode deleteDuplicates2 (ListNode head) {
        // write code here
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        ListNode cur = newHead;
        while(cur.next != null && cur.next.next != null) {
            if(cur.next.val == cur.next.next.val) {
                int tempVal = cur.next.val;
                while(cur.next != null && tempVal == cur.next.val) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }

        return newHead.next;
    }

    /**
     * 链表转数组要求第i位的数是比链表中第i位大的第一个数字，如果没有则设置成0
     *
     * 输入 5 -> 2 -> 3 -> 4 -> 6
     * 输出 [6, 3, 4, 6, 0]
     * */
    public int[] convert(ListNode head, int n) {
        int[] res = new int[n];
        if(res.length < 2) {
            return res;
        }
        ListNode p1 = head;
        ListNode p2 = p1.next;
        int curVal = head.val;
        int curIdx = 0;
        while (p1 != null) {
            while (p2 != null) {
                if (p2.val > curVal) {
                    res[curIdx] = p2.val;
                    break;
                }
                p2 = p2.next;
            }
            p1 = p1.next;
            if(p1 != null) {
                p2 = p1.next;
                curVal = p1.val;
                curIdx ++;
            }
        }

        return res;
    }



}
